package pro.softzhang.algo.lc600;

import pro.softzhang.algo.common.TrieNode;

import java.util.List;

public class LC648_ReplaceWords {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public String replaceWords(List<String> dictionary, String sentence) {
            TrieNode root = buildTrie(dictionary);
            StringBuilder sb = new StringBuilder();

            String[] words = sentence.split(" ");
            for (int i = 0; i < words.length; i++) {
                String prefix = findPrefix(root, words[i]);
                if(!prefix.isEmpty()) {
                    words[i] = prefix;
                }
            }
            return String.join(" ", words);
        }

        private TrieNode buildTrie(List<String> dict) {
            TrieNode root = new TrieNode();
            for (String word : dict) {
                TrieNode node = root;
                for (char ch : word.toCharArray()) {
                    int idx = ch - 'a';
                    if(node.children[idx] == null) {
                        node.children[idx] = new TrieNode();
                    }
                    node = node.children[idx];
                }
                node.isWord = true;
            }
            return root;
        }

        private String findPrefix(TrieNode root, String word) {
            TrieNode node = root;
            StringBuilder sb = new StringBuilder();
            for (char ch : word.toCharArray()) {
                int idx = ch - 'a';
                if(node.isWord || node.children[idx] == null) {
                    break;
                }
                sb.append(ch);
                node = node.children[ch - 'a'];
            }
            return node.isWord ? sb.toString() : "";
        }
    }
}
